using System;
using System.Collections.Generic;

namespace DependencyAnalysis.Algorithms.CycleDetection
{
    internal class TarjanCycleDetection
    {
        private IList<IList<DependencyNode>> _stronglyConnectedComponents;
        private Stack<DependencyNode> _stack;
        private int _index;

        public IList<IList<DependencyNode>> ReportCycles(IList<DependencyNode> graph)
        {
            _stronglyConnectedComponents = new List<IList<DependencyNode>>();
            _index = 0;
            _stack = new Stack<DependencyNode>();
            foreach (DependencyNode v in graph)
            {
                if (v.CycleIndex < 0)
                {
                    FindLinks(v);
                }
            }
            return _stronglyConnectedComponents;
        }

        private void FindLinks(DependencyNode v)
        {
            v.CycleIndex = _index;
            v.LowLink = _index;
            _index++;
            _stack.Push(v);

            foreach (var w in v.Dependencies)
            {
                if (w.CycleIndex < 0)
                {
                    FindLinks(w);
                    v.LowLink = Math.Min(v.LowLink, w.LowLink);
                }
                else if (_stack.Contains(w))
                {
                    v.LowLink = Math.Min(v.LowLink, w.CycleIndex);
                }
            }

            if (v.LowLink != v.CycleIndex) return;
            ConvertToNodes(v);
        }

        private void ConvertToNodes(DependencyNode v)
        {
            var scc = new List<DependencyNode>();
            DependencyNode x;
            do
            {
                x = _stack.Pop();
                scc.Add(x);
            } while (v != x);
            if (scc.Count > 1)
            {
                _stronglyConnectedComponents.Add(scc);
            }
        }
    }
}